%!TEX root = main.tex

\makeatletter{}\section{Introduction}

Tables on the Web have been recognized as an important source of structured data and have 
attracted a number of research efforts from both academia and 
industry~\cite{cafarella2008uncovering,gupta11,wang2012understanding}. All of those works extract tables 
individually, and focus on annotating the tables for applications such as 
visualization, search, and knowledge base enrichment.  While understanding raw tables 
independently is important, there is even more value in consolidating individual tables. 

As an example, consider the set of tables at the Public School Review
Site\footnote{http://www.publicschoolreview.com/}. They record the
statistics of schools all over the USA, as shown in Figure
\ref{fig:schools}. For human readability, the site designers have
fragmented the information into smaller tables where each table
corresponds to a subset of the schools. However, a user might be
interested in a different organization of the schools, such as finding
all schools with over 500 students. Without a holistic view of the
original table of all schools, such a task is nearly impossible to
accomplish.  Furthermore, realizing that these tables are part of a
bigger whole can enable a table search engine to provide much more
advanced utilities such as visualizing the schools by states or school
types.

%/FieldENG2012.html; 
% http://www.shanghairanking.com/FieldENG2011.html;
%http://www.shanghairanking.com/FieldENG2010.html;

\begin{figure*}[ht]
\begin{center}
\includegraphics[width=18cm]{pics/schools.pdf}
\caption{Screenshots of the Public School Review Website.}
\label{fig:schools}
\end{center}
\end{figure*}

\begin{figure*}[ht]
\begin{center}
\includegraphics[width=18cm]{pics/overview-full.pdf}
\caption{Table stitching. (Left) Raw tables and their context. (Right) An ideal synthesized table from the raw tables.}
\label{fig:overview}
\end{center}
\end{figure*}

This example demonstrates the power of {\em table synthesis}, i.e., combining raw tables 
on the Web to produce union tables that are {\em more valuable than the sum of those individual tables}.  In 
this paper, we provide a first step to the solution of this novel
problem.  We consider the 
problem of {\em table stitching}: combining multiple tables that are
on the {\em same} site and have the 
same schema, thus can be considered parts of a larger union table.   
Even this first step raises challenging technical problems.  First, we must correctly discover tables that 
can be unioned. Second, we need to stitch the tables properly. Specifically, simply 
concatenating raw tables together will lead to a table that contains inconsistent data. In the example site 
shown in Figure~\ref{fig:schools}, schools from different locations
may have the same name. To properly combine them, we must recover
their locations from the page context (e.g., the page title, or text
surrounding the table) and add it as another column in
the table. In our example, the result of 
ideal stitching is shown on the right panel of Figure \ref{fig:overview}.

%Take Figure \ref{fig:overview} as an example. Looking at the left of the figure, we have a set of Web tables 
%extracted from different Web pages, each of which lists the statistics of schools in some area and all of 
%which share the same set of headers.

%She need to look at other places to disambiguate the schools. 
%We will address these issues by providing a unified view of all these tables with additional metadata 
%information (e.g. ).

In this paper, we describe algorithms for finding stitchable/unionable tables, recovering the hidden attributes, and assigning them meaningful column names. Our main contributions are the following:

\begin{itemize}

\item We introduce the table stitching problem whose goal is to structurally organizing individual tables with 
necessary context. 

\item We describe a segment-based multiple sequence alignment algorithm for extracting hidden table 
attributes from the table context, where each table context is considered as a sequence. Given candidate 
segments from different heuristics as input, the algorithm seeks an optimal alignment of multiple sequences 
and determines the proper segmentations of those sequences.

\item We describe techniques for giving the newly extracted attributes
  meaningful names. 

\item We present a set of experiments that show: 1) our method effectively extracts better 
hidden attributes than baseline methods; 2) a combination of candidate segments suggested by different 
heuristics works the best; and 3) we are able to automatically label extracted attributes with a set of 
predefined class labels with reasonable quality.

\end{itemize}

We define the terminology and the table stitching problem in Section~\ref{sec:problem}.
Section~\ref{sec:metadata} describes the core of our technique, namely extracting hidden attributes 
from table contexts. Together with the technique for assigning meaningful column names for those 
attributes (which we briefly describe within the experimental evaluation), this
technique allows us to provide a first-cut solution for table synthesis. Experimental results are presented 
in Section~\ref{sec:exp}, followed by a discussion on related work in Section~\ref{sec:related}. Finally, 
Section~\ref{sec:conclusion} concludes and proposes some future directions.
